974. Флойд – 1

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между всеми парами его вершин. Гарантируется, что в графе нет циклов отрицательного веса.

Вход. В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел – матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы стоят нули.

Выход. Выведите n строк по n чисел – матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Пример входа	Пример выхода
4 0 5 9 100 100 0 2 8 100 100 0 7 4 100 100 0	0 5 7 13 12 0 2 8 11 16 0 7 4 9 11 0

РЕШЕНИЕ

графы – алгоритм Флойда-Уоршела

Анализ алгоритма

В задаче необходимо построить матрицу кратчайших путей между всеми парами вершин графа. Для этого следует реализовать алгоритм Флойда – Уоршела.

Пример

Граф, приведенный в условии, имеет вид:

Реализация алгоритма

Матрицу смежности графа храним в массиве g.

#define MAX 101

int g[MAX][MAX];

Функция floyd реализует алгоритм Флойда – Уоршела.

void floyd(void)

{

int i, j, k;

for(k = 0; k < n; k++)

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

if (g[i][k] + g[k][j] < g[i][j]) g[i][j] = g[i][k] + g[k][j];

}

Основная часть программы. Читаем входной граф.

scanf("%d",&n);

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

scanf("%d",&g[i][j]);

Запускаем алгоритм Флойда – Уоршела.

floyd();

Выводим матрицу кратчайших расстояний между всеми парами вершин.

for(i = 0; i < n; i++)

{

for(j = 0; j < n; j++)

printf("%d ",g[i][j]);

printf("\n");

}

Java реализация

import java.util.*;

public class Main

{

static int g[][];

static int n;

static void floyd()

{

for(int k = 0; k < n; k++)

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

if (g[i][k] + g[k][j] < g[i][j])

g[i][j] = g[i][k] + g[k][j];

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

n = con.nextInt();

g = new int[n][n];

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

g[i][j] = con.nextInt();

floyd();

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

System.out.print(g[i][j] + " ");

System.out.println();

}

con.close();

}

}

Python реализация

Функция floyd реализует алгоритм Флойда – Уоршела.

def floyd():

for k in range(n):

for i in range(n):

for j in range(n):

if g[i][k] + g[k][j] < g[i][j]:

g[i][j] = g[i][k] + g[k][j]

Основная часть программы. Читаем входной граф.

n = int(input())

g = [[] for _ in range(n)]

for i in range(n):

g[i] = list(map(int, input().split()))

Запускаем алгоритм Флойда – Уоршела.

floyd()

Выводим матрицу кратчайших расстояний между всеми парами вершин.

for i in range(n):

print(*g[i])